
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 45. 二叉树的后序遍历
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 * todo 144. 二叉树的前序遍历
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 * todo 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0229 {

    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;

    }

    //二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        preorder(root,values);
        return values;
    }
    private void preorder(TreeNode root,List<Integer> values){
        if (root == null)return;
        values.add(root.val);
        preorder(root.left,values);
        preorder(root.right,values);
    }

    //二叉树的后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        postorder(root,values);
        return values;
    }
    private void postorder(TreeNode root,List<Integer> values){
        if (root == null)return;
        postorder(root.left,values);
        postorder(root.right,values);
        values.add(root.val);
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(4);
        TreeNode t = new TreeNode(2,one,two);
        TreeNode q = new TreeNode(14);
        TreeNode w = new TreeNode(15,q,null);
        TreeNode e = new TreeNode(9);
        TreeNode r = new TreeNode(13,e,w);
        TreeNode root = new TreeNode(6,t,r);
        Solution0229 test = new Solution0229();
        List<Integer> queries = Arrays.asList(2,5,16);
    }

}

